import com.sun.deploy.net.MessageHeader;
import javafx.scene.layout.Priority;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024 —05 —12
 * Time: 21:15
 */
class Imp implements Comparator<Integer>{  // 接口实现Comparator 并重写compare方法
    @Override
    public int compare(Integer o1, Integer o2) {
        //return o1.compareTo(o2);//小跟堆
        //return (o2 > o1 ? o2 : o1 );
        return o2.compareTo(o1);
    }
}
public class Test {
    public int[] smallestK (int[] array , int k){
        int[] ret = new int[k];
        if(ret ==  null || k < 0){
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Imp());//传入重写的比较器（大根堆建立）
       /*另一种写法
       PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });*/


        //Nlogk
        for (int i = 0 ; i < k ; i++){
            priorityQueue.offer(array[i]);//先建立一个usedsize = k 的大根堆
        }
        //(N-k)logk    //Nlogk+(N-k)logk = Nlogk
        for (int j = k; j < array.length ; j++) {
            int top = priorityQueue.peek();
            if (array[j] < top){        //数组第k个元素跟大根堆堆顶元素进行比较，若小，则出堆，再进进堆
                priorityQueue.poll();
                priorityQueue.offer(array[j]);
            }
        }
        for (int i = 0 ; i < k ; i++){
            ret[i] = priorityQueue.poll();          //最后得到的大根堆里面存的元素就是这个数组中最小的k个数
        }
        System.out.println(Arrays.toString(ret));
        return ret;
    }

    public static void main4(String[] args) {
        Test test = new Test();
        int[] array = new int[]{13,22,54,34,23,56,12};
        test.smallestK(array , 3 );
    }
    public static void main3(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue();
         int[] array = new int[]{13,22,54,34,23,56,12};
        for (int i = 0; i < array.length; i++) {
            priorityQueue.offer(array[i]);//priorityQueue默认建立的是小跟堆
        }
        int k = 3;
        int[] array2 = new int[k];
        for(int i = 0; i < k ; i++){
            array2[i] =priorityQueue.poll();
        }

        System.out.println(Arrays.toString(array2));

    }
    public static void main2(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(15);
        priorityQueue.offer(1);
        priorityQueue.offer(12);
        System.out.println(priorityQueue.peek());

    }

    public static void main(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = new int[]{27,15,19,18,28,34,65,49,25,37};
        testHeap.initiateElem(array); //对elem进行初始化
        testHeap.creatHeap();
        System.out.println();


        System.out.print("对堆进行排序");
        testHeap.heapSort();


        System.out.println();
        System.out.print("出一个元素后");
        testHeap.pop();
        testHeap.creatHeap();

        System.out.println();
        System.out.print("插入元素后");
        testHeap.push(99);
        testHeap.creatHeap();
    }
}

